#include<stdio.h>
#include<string.h>
#include <iostream>

#define MAX 20001

using namespace std;

// probar operadores de relacion

class Bigint{
   public:
      int num[MAX+1];
      int offset;

      Bigint() {  
         offset = MAX - 1;
         memset(num, 0, sizeof(num));
      }
 
      Bigint(char n[]) {
         offset = MAX - strlen(n);
         memset(num, 0, sizeof(int[offset]));
      
         for(int i = offset; i < MAX; i++){
            num[i] = n[i-offset] - '0';
         }
      }
      
      bool operator>(const Bigint& ) const;
		bool operator<(const Bigint& ) const;
		bool operator>=(const Bigint& ) const;
		bool operator<=(const Bigint& ) const;
		bool operator==(const Bigint& ) const;
		bool operator!=(const Bigint& ) const;
		
      void operator<<=(const int );
};

bool Bigint::operator>(const Bigint &b) const{
   if(offset != b.offset)
      return offset < b.offset;

   int ds = offset;

   while (ds < MAX && num[ds] == b.num[ds]) ds++;

   if(ds == MAX) return false;

   return num[ds] > b.num[ds];
}

bool Bigint::operator<(const Bigint &b) const{
   if(offset != b.offset)
      return offset > b.offset;

   int ds = offset;

   while (ds < MAX && num[ds] == b.num[ds]) ds++;

   if(ds == MAX) return false;

   return num[ds] < b.num[ds];
}

bool Bigint::operator>=(const Bigint &b) const{
   if(offset != b.offset)
      return offset < b.offset;

   int ds = offset;

   while (ds < MAX && num[ds] == b.num[ds]) ds++;

   if(ds == MAX) return true;

   return num[ds] > b.num[ds];
}

bool Bigint::operator<=(const Bigint &b) const{
   if(offset != b.offset)
      return offset > b.offset;

   int ds = offset;

   while (ds < MAX && num[ds] == b.num[ds]) ds++;

   if(ds == MAX) return true;

   return num[ds] < b.num[ds];
}

bool Bigint::operator==(const Bigint &b) const{
   if(offset != b.offset){
      return false;
   }

   int ds = offset;

   while (ds < MAX && num[ds] == b.num[ds]) ds++;

   return ds == MAX;
}

bool Bigint::operator!=(const Bigint &b) const{
   if(offset != b.offset){
      return true;
   }

   int ds = offset;

   while (ds < MAX && num[ds] == b.num[ds]) ds++;

   return ds < MAX;
}

void Bigint::operator<<=(const int d){
   if(num[offset] == 0) return;

   int i = offset - d;
   int limit = MAX - d;
   for(; i < limit; i++)
      num[i] = num[i + d];
   for(; i < MAX; i++)
      num[i] = 0;
   offset -= d;
}

void copy(const Bigint &a, Bigint &r){
   r.offset = a.offset;
   memcpy(r.num, a.num, sizeof(a.num));
}

/*
 * Imprimir un Bigint
 */
void print(Bigint &b){
   int size = MAX - b.offset + 1, index = 0;
   char num_print[size];

   for(int i = b.offset; i < MAX; i++){
      num_print[index++] = b.num[i] + '0';
   }
   num_print[index] = '\0';
   
   printf("%s",num_print);
}

/*
 *  Operación de adición
 */
void add(const Bigint &a, const Bigint &b, Bigint &r){
   int carry = 0;
   r.offset = min(a.offset, b.offset) - 1;   

   for(int i = MAX-1; i >= r.offset; i--){
      r.num[i] = a.num[i] + b.num[i] + carry;
      carry = r.num[i] / 10;
      r.num[i] = r.num[i] - 10 * carry;
   }
   
   if(r.num[r.offset] == 0 ) {
      r.offset++;
   }
}

/*
 * Operación de sustracción
 */
void sub2(Bigint &a, Bigint &b, Bigint &r){
   Bigint bb;
   copy(b, bb);
   
   for(int i = MAX-1; i >= a.offset; i--){
      bb.num[i] = 9 - bb.num[i];
   }
   
   bb.num[MAX-1]++; 
      
   add(a, bb, r);
     
   r.num[a.offset-1] = 0; // ver si es necesario..

   while(r.num[r.offset] == 0 && r.offset < MAX - 1) {
      r.offset++;  
   }      
}

/**
PRE: 
POST:

@TO_DO: implementar el sistema de comentarios
**/

void sub(const Bigint &a, const Bigint &b, Bigint &r){
	int i = MAX - 1, temp, borrow = 0;

	for(; i >= a.offset; i--){
      temp = a.num[i] - borrow;
      
	   if(i >= b.offset) {
	      temp -= b.num[i];
	   } 

		if(a.num[i] > 0){
			borrow = 0;
	   }
	   
		if(temp < 0){
			temp += 10;
			borrow = 1;
		}
		
		r.num[i] = temp;
	}

	r.offset = a.offset;

   while (r.num[r.offset] == 0 && r.offset < MAX - 1) {
      r.offset++;  
   }
}

void mul(const Bigint &a, const Bigint &b, Bigint &r){
   if (b.offset < a.offset) {
      mul(b,a,r);
      return;
   }
   
   int carry, carryR, ia, tmp, ds = 0;
   for(int ib = MAX-1; ib >= b.offset; ib--){
      ia = MAX-1;
      carry = carryR = 0;
         
      for( ; ia >= a.offset; ia--){
         tmp = b.num[ib] * a.num[ia] + carry;                                   
         carry = tmp / 10;                                                                   
         r.num[ia - ds] += tmp - 10 * carry + carryR; // tmp % 10 = tmp - 10*carry             
         carryR = r.num[ia - ds] / 10;     
         r.num[ia - ds] = r.num[ia - ds] - 10 * carryR; // r.num[ia - ds] %= 10;               
      }

      r.num[ia - ds] = carry + carryR;
      ds++;
   }

   r.offset = ia - ds;
   while(r.num[r.offset] == 0 && r.offset < MAX - 1){
      r.offset++;
   }
}

void div(const Bigint &a, const Bigint &b, Bigint &r){	
	if(b.offset == MAX-1 && b.num[MAX-1] == 0){
		cout << "ERROR: division por cero" << endl;
		return;
	}
	
	if(a < b)
		return; // Acordarse que r es igual a 0 siempre que se pasa a una operacion
	
	Bigint row, tmp;
	
	for(int i=a.offset; i<MAX; i++){
		row <<= 1;
		row.num[MAX-1] = a.num[i];
		r <<= 1;
		
		while(row >= b){
			r.num[MAX - 1]++;
			sub(row, b, tmp);
			row = tmp;
      }
	}
}



